package mine.code.day.year2021.month08;

import org.junit.Test;

/**
 * 可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：
 * 'A'：Absent，缺勤
 * 'L'：Late，迟到
 * 'P'：Present，到场
 * 如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：
 * <p>
 * 按 总出勤 计，学生缺勤（'A'）严格 少于两天。
 * 学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（'L'）记录。
 * 给你一个整数 n ，表示出勤记录的长度（次数）。请你返回记录长度为 n 时，可能获得出勤奖励的记录情况 数量 。答案可能很大，所以返回对 10^9 + 7 取余 的结果。
 * <p>
 * 示例 1：
 * <p>
 * 输入：n = 2
 * 输出：8
 * <p>
 * 解释：
 * 有 8 种长度为 2 的记录将被视为可奖励：
 * "PP","AP", "PA", "LP", "PL", "AL", "LA", "LL"
 * 只有"AA"不会被视为可奖励，因为缺勤次数为 2 次（需要少于 2 次）。
 * <p>
 * 示例 2：
 * <p>
 * 输入：n = 1
 * 输出：3
 * <p>
 * 示例 3：
 * <p>
 * 输入：n = 10101
 * 输出：183236316
 * <p>
 * 示例 4：
 * <p>
 * 输入：n = 3
 * 输出：19
 * <p>
 * 解释：
 * "PPP","PPA","PPL",
 * "APP","APL",
 * "PAP","PAL","LPP",
 * "LPL","LPA",
 * "PLA","PLP","PLL",
 * "ALL","ALP",
 * "LAL","LAP",
 * "LLA","LLP"
 * 示例 5：
 * <p>
 * 输入：n = 4
 * <p>
 * PPPP,PPPA,PPPL,
 * PPAP,PPAL,
 * PPLA,PPLL,PPLP,
 * APPL,APPP,
 * APLL,APLP,
 * PAPL,PAPP,
 * PALL,PALP,
 * LPPL,LPPA,LPPP,
 * LPLL,LPLP,LPLA,
 * LPAP,LPAL,
 * PLAL,PLAP,
 * PLPA,PLPP,PLPL,
 * PLLA,PLLP,
 * ALLP,
 * ALPL,ALPP,
 * LALP,LALL,
 * LAPL,LAPP,
 * LLAL,LLAP,
 * LLPA,LLPP,LLPL
 *
 * @author caijinnan
 */
public class Day18_学生出勤记录II {

    @Test
    public void run() {
        System.out.println(checkRecord(10101));
    }

    // 372422835
    // 183236316
    int mod = 1000000007;

    public int checkRecord(int n) {
        // dpall[i] = dpal[i-1]
        // dpal[i] = dpa[i-1]
        // dpa[i] = dpll[i-1]+dpl[i-1]+dp[i-1]+dpall[i-1]+dpal[i-1] + dpa[i-1]
        // dpll[i] = dpl[i-1]
        // dpl[i] = dp[i-1]
        // dp[i] = dpll[i-1]+dpl[i-1]+dp[i-1]
        // 含有a,结尾是LL
        long[] dpall = new long[n];
        // 含有a,结尾是L
        long[] dpal = new long[n];
        // 含有A,结尾不是L和LL
        long[] dpa = new long[n];
        // 不含A 结尾是LL
        long[] dpll = new long[n];
        // 不含A 结尾是L
        long[] dpl = new long[n];
        // 不含A 结尾不是L和LL
        long[] dp = new long[n];
        dpa[0] = 1;
        dpl[0] = 1;
        dp[0] = 1;
        for (int i = 1; i < n; i++) {
            dpall[i] = dpal[i - 1] % mod;
            dpal[i] = dpa[i - 1] % mod;
            dpa[i] = (dpll[i - 1] + dpl[i - 1] + dp[i - 1] + dpall[i - 1] + dpal[i - 1] + dpa[i - 1]) % mod;
            dpll[i] = dpl[i - 1] % mod;
            dpl[i] = dp[i - 1] % mod;
            dp[i] = (dpll[i - 1] + dpl[i - 1] + dp[i - 1]) % mod;
        }
        int num = n - 1;
        long l = dpall[num] + dpal[num] + dpa[num] + dpll[num] + dpl[num] + dp[num];
        return (int)(l % mod);
    }
}
